/**
 * 给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
 * https://leetcode.cn/problems/unique-binary-search-trees-ii/
 */
class GenerateTrees {
    public List<TreeNode> generateTrees(int n) {
        return build(1,n);
    }
    public List<TreeNode> build(int lo,int hi) {
        List<TreeNode> res=new LinkedList<>();
        if(lo>hi) {
            res.add(null);
            return res;
        }
        for(int i=lo;i<=hi;i++) {
            List<TreeNode> left=build(lo,i-1);
            List<TreeNode> right=build(i+1,hi);
            for(TreeNode leftChild:left) {
                for(TreeNode rightChild:right) {
                      TreeNode root=new TreeNode(i);
                    root.left=leftChild;
                    root.right=rightChild;
                    res.add(root);
                }
            }
        }
        return res;
    }
}